Pattern search is a simple yet powerful machine vision tool. Given a template pattern and an image, its objective is to find all instances of the pattern in the image. It involves two steps, a search step and a match step. The search step places the pattern at all valid poses (locations, rotation angles), and scales of the image being searched. The match step determines the goodness of the match between the pattern at a given pose and scale and the subset of the image corresponding to the pose and scale. The normalized correlation method (Ballard DH and Brown CM, “Computer Vision”, Prentice Hall 1982, pp. 68–70) of fixed rotation and scale has been widely used as the matching method in many machine vision applications. The match score of normalized correlation is largely independent of linear variations in object shading caused by reflectivity or illumination variations. However, pattern search based on a normalized correlation method is inherently computationally demanding since it requires operations between two (pattern and image) two-dimensional regions on all valid image locations. Even with the state-of-the-art computers, it is still difficult to achieve real-time performance when the image or pattern size is large. Furthermore, it does not work well when the pattern being searched is subject to rotation and/or size/aspect ratio variations. The match score could drop significantly even if only a few degrees of rotation or a few percent of size change occurs. One prior art approach to rotation and scale invariance is to rotate and scale the pattern template and try all possible scale and rotation combinations. However, this imposes an even greater computational demand that cannot be accomplished using normalized correlation.
Another prior art approach is the use of a geometric pattern matching method such as PatMax introduced by Cognex (Silver B, “Geometric Pattern Matching for General-Purpose Inspection in Industrial Machine Vision”, Intelligent Vision '99 Conference, Jun. 28–29, 1999). This approach uses geometric information in place of pixel grid-based correlation. For example, it interprets a square as four line segments and a football as two arcs. It extracts key geometric features within an object image such as boundary encoding and measures characteristics such as shape, dimensions, angle, arcs, and shading. It then corresponds the spatial relationships between the key features of the pattern template and the new image. However, this prior art approach requires high edge contrast and low noise between patterns and background to reliably extract the key geometric features. It fails when edges of a pattern are not well defined. This is the inherent problem when using the geometric approach in place of any pixel grid based approach.
A rotation and scale invariant pattern matching method was disclosed (Shih-Jong J. Lee et. al., “A Rotation and Scale Invariant Pattern Matching Method”, U.S. patent application Ser. No. 09/895,150 filed Apr. 10, 2002) that generates a polar coordinate representation of the pattern template image thereby allowing for fast linear search of scale along the radius axis and a search for rotation angle along the angular axis. Fast search is achieved by projecting image intensities into the radius axis for scale search and projecting image intensities into the angular axis for rotation angle search. However, this method requires that the polar coordinate transformation be performed on each image region where the rotation and scale invariant pattern matching method is applied. This is especially time consuming if image regions centered at all positions of an image are subjected to the search. It is desirable to have a fast initial invariant search method that quickly identifies a reduced set of image positions where the finer rotation and scale invariant pattern matching method could be applied.
Furthermore, the speed of prior art invariant search methods depends on the range of rotation angles that need to be searched. It is time consuming when the rotation angle search range is large. It is desirable to have an invariant search method that does not depend on the rotation angle search range.
A fast regular shaped pattern search method was disclosed (Lee, Shih-Jong J. et. al., “Fast Regular Shaped Pattern Searching”, U.S. patent application Ser. No. 10/255,016 filed on Sep. 24, 2002) that performs fast pattern matching with flexible projection kernels to construct regular-shaped patterns using an accumulation method. Other prior art methods were disclosed (Lee, Shih-Jong J., Oh, S, Kim, D. “Fast Pattern Searching,” U.S. patent application Ser. No. 10/283,380, filed on October, 2002; Lee, Shih-Jong J, Oh, S “Fast Invariant Pattern Search”, U.S. patent application Ser. No. 10/302,466, filed on November, 2002) that teach a fast invariant search method for initial detection of the match candidates using rotation and scale invariant profiles. The rotation invariant contours of the invention achieve fast rotation invariant search that is independent of the rotation angle search range. However, the circular shaped rotation invariant contours do not fit well on pattern templates, which are not compact shaped such as elongated shape. To avoid covering regions outside the template, only a small compact region inside the template could be used. This could result in a large number of false or missed matches. Furthermore, the prior art approach is not designed for partial pattern matching so it may not achieve reliable results when the object of interest is partially occluded or has missing parts. It is highly desirable to have a new method that preserves a favorable speed advantage yet could handle non-compact templates and could support reliable partial pattern search.